package katas.recursion;

import java.util.HashSet;
import java.util.Set;

public class CoinChange {
	
	public static void getChange(int n, Integer[] coins, int sum, Set<Integer[]> list){
		if(sum == n)
			list.add(coins);
		else{
			if(sum + 25 <= n){
				coins[0]++;
				getChange(n, coins, sum + 25, list);
				coins[0]--;
			}
			if(sum + 10 <= n){
				coins[1]++;
				getChange(n, coins, sum + 10, list);
				coins[1]--;
			}
			if(sum + 5 <= n){
				coins[2]++;
				getChange(n, coins, sum + 5, list);
				coins[2]--;
			}
			if(sum + 1 <= n){
				coins[3]++;
				getChange(n, coins, sum + 1, list);
				coins[3]--;
			}
		}
	}
	
	public static void main(String[] args) {
		Set<Integer[]> set = new HashSet<Integer[]>();
		Integer[] coins = {0,0,0,0};
		CoinChange.getChange(10, coins, 0, set);
		System.out.println(set.size() + " ways.");
	}
}
